package com.sicheng.lc.周赛.分类.位运算;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/24 18:17
 */
public class 优质数对的数目 {
    //https://leetcode.cn/problems/number-of-excellent-pairs/
    public long countExcellentPairs(int[] nums, int k) {
        nums = Arrays
                .stream(nums)
                .distinct()
                .toArray();
        int[] cnt = new int[30];
        for (int x : nums) {
            cnt[bitCount(x)]++;
        }
        int sum = 0;
        for (int i = k; i < cnt.length; i++) {
            sum += cnt[i];
        }
        long res = 0;
        for (int i = 0; i < cnt.length; i++) {
            res += (long) sum * cnt[i];
            if (k - i - 1 >= 0 && k - i - 1 < 30)
                sum += cnt[k - i - 1];
        }

        return res;
    }

    int bitCount(int x) {
        int cnt = 0;
        while (x > 0) {
            x &= (x - 1);
            cnt++;
        }
        return cnt;
    }
}
